package PQ;

use POSIX qw(ceil floor);
@ISA = qw(Exporter);
@EXPORT = qw();

sub new {
	my($this) = [];
	my($classname) = shift;

	bless $this;
	return $this;
}

sub push_heap {
	my($this) = shift;
	my($object) = shift;
	my($priority) = shift;
	my($arraySize);
	my($elementPos,$parentPos);
	my($tempEle);

	$arraySize = $#$this + 1;

	$this->[$arraySize]->{'object'} = $object;
	$this->[$arraySize]->{'priority'} = $priority;
	$elementPos = $arraySize;

	while($elementPos>0) {
		$parentPos = ceil($elementPos/2)-1;
		if($this->[$elementPos]->{'priority'}>$this->[$parentPos]->{'priority'}) {
			$tempEle = $this->[$parentPos];
			$this->[$parentPos] = $this->[$elementPos];
			$this->[$elementPos] = $tempEle;

			$elementPos = $parentPos;
		}
		else {
			last;
		}
	}
}

sub pop_heap {
	my($this) = shift;
	my($object) ;
	my($priority);
	my($tempEle) ;
	my($elementPos,$childPos);
	my($swapPos);

	if($#$this==-1) {
		print STDERR "Heap is empty\n";
	} 

	$object = $this->[0]->{'object'};
	$priority = $this->[0]->{'priority'};

	$this->[0] = $this->[$#$this];
	pop(@{$this});

	$arraySize = $#$this+1;
	#Heapify
	$elementPos = 0;

	#print STDERR " Popping $arraySize\n";
	while($elementPos<$arraySize) {
		$child1Pos = 2*$elementPos+1;
		$child2Pos = 2*$elementPos+2;
		
		$swapPos = $elementPos;

		if($child1Pos<$arraySize && $this->[$swapPos]->{'priority'}<$this->[$child1Pos]->{'priority'}) {
			$swapPos = $child1Pos;
		}

		if($child2Pos<$arraySize && $this->[$swapPos]->{'priority'}<$this->[$child2Pos]->{'priority'}) {
			$swapPos = $child2Pos;
		}

		if($swapPos == $elementPos) {
			last;
		}
		else {
			$tempEle = $this->[$swapPos];
			$this->[$swapPos]=$this->[$elementPos];
			$this->[$elementPos] = $tempEle;

			$elementPos = $swapPos;
		}
		
	}
	return ($object,$priority);
}

sub empty {
	my($this) = shift;
	if($#$this==-1) {
		return 1;
	}
	else {
		return 0;
	}
}

sub print_heap {
	my($this) = shift;
	my($i);
	for($i=0;$i<=$#$this;$i++) {
		print $this->[$i]->{'object'}."(".$this->[$i]->{'priority'}.") ";
	}
	print "\n";
}

1;
